1. Field of the Invention
The present invention relates to a method for image de-blurring, based on estimating an image's Lipschitz exponent a using a direct computational technology rather than an iterative technique. More particularly, the method of the present invention is related to de-blurring of an image based on singular integrals and Fast Fourier Transform (FFT) algorithms.
2. Description of the Related Art
Most images ƒ(x, y) are not differentiable functions of the space variables x and y. Rather, they exhibit edges, singularities, localized sharp features, and various other kinds of important fine-scale details or texture. For such non-smooth imagery, prior art has generally formulated the ill-posed image-deblurring problem incorrectly. This often leads to flawed reconstructions, where vital small-scale information has been smoothed out, or where unexpected noise-induced graininess obscures fine detail.
Digital image acquisition plays an ever-increasing role in science, technology, and medicine, and image deblurring is becoming an increasingly important image processing activity. In addition, with the widespread use of digital cameras and camera cell-phones, there is growing general interest in the possibilities of post-processed digital image enhancement. In another direction, wavefront coding is a revolutionary new idea in Optics that calls for deliberately designing an imperfect lens, see, e.g., D. MacKenzie, Novel Imaging Systems Rely On Focus-Free Optics, SIAM News, Volume 36#6, July-August 2003, the contents of which are hereby incorporated by reference in their entirety. That lens produces a blurred image, but one where the depth of field has been significantly increased. Mathematical deconvolution is subsequently applied to the blurred image to remove the designed blur. This results in a superior photograph where distant and close-in objects are equally well focused. Carl Zeiss Inc., is reportedly set to manufacture such a lens. In these applications, fast computational throughput for large size imagery is very desirable. Some deconvolution methods involve computationally intensive nonlinear iterative procedures, typically requiring hours of computing time. Direct (non-iterative) deconvolution methods, that can process 1000×1000 images in less than a minute of computing time, are considered real-time methods, and are highly sought after.
Image deblurring is a difficult ill-posed mathematical problem, requiring for its correct solution prior knowledge and specification of the smoothness characteristics in the unknown exact sharp image ƒ(x, y). However, most commonly occurring images are not differentiable functions of the space variables x and y. Rather, these images display edges, localized sharp features, and various other fine-scale details or texture. For such non-smooth imagery, prior art has generally stabilized the ill-posed deblurring problem by prescribing L2 bounds for the sharp image ƒ(x, y). The L2-Tikhonov-Miller method, is the best-known example of that approach, see, e.g., K. Miller, Least Squares Methods For Ill-Posed Problems With A Prescribed Bound, SIAM J. Math. Anal., 1 (1970), pp 52-74; R. L. Lagendijk and J. Biemond, Iterative Identification and Restoration of Images, Kluwer Academic Publisher, Norwell, Mass., 1991, the contents of both of which are hereby incorporated in their entirety. In another direction, considerable research during the last ten years has been based on the assumption that images belong to BV(R2), the space of functions of bounded variation. This has led to nonlinear partial differential equation (PDE) deblurring procedures, where bounds are prescribed on the total variation or TV seminorm
      ∫          R      2        ⁢                          ∇        f                    ⁢          ⅆ      x        ⁢                  ⅆ        y            .      The Marquina-Osher TV algorithm is one of the most widely used PDE deblurring methods, see, e.g., Marquina-Osher, Explicit Algorithms For A New Time Dependent Model Based On Level Set Motions For Nonlinear Deblurring And Noise Removal, SIAM J. Sci. Comput., 22 (2000), pp. 387-405, the contents of which are hereby incorporated in their entirety. However, each of these two general deblurring approaches is fundamentally flawed theoretically, and that flaw often translates into poor quality reconstructions. Thus, prescribing L2 bounds insufficiently constrains the Tikhonov-Miller solution, which is typically found to be contaminated by noise. Also, as was recently proved, most natural images are not of bounded variation, see Y. Gousseau and J. M. Morel, Are Natural Images of Bounded Variation?, SIAM J. Math Anal., 33 (2001), pp. 634-648, the contents of which are hereby incorporated by reference in their entirety. As a result, Marquina-Osher TV deblurring often leads to unacceptable loss of fine-scale information.
Correct characterization and calibration of the lack of smoothness of images is crucial in image deblurring, as well as in other image processing tasks. As functions of x and y, most images are significantly better behaved than the most general L2 functions, while being significantly less smooth than functions of bounded variation. For this reason, both the L2-Tikhonov-Miller and TV-Marquina-Osher methods are incorrectly formulated.